package com.veal98.stack_queue;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequentElements_347 {

    public int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return new int[0];
        }

        // 存储最终结果
        int[] res = new int[k];

        // 计算每个元素出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) +  1);
        }

        // 构造小顶堆
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(
                (o1, o2) -> o1.getValue() - o2.getValue()
        );
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            priorityQueue.offer(entry);
            // 每次弹出堆顶元素（出现频率最低的元素），直到堆中留下的元素个数为 k 个
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }

        for (int i = 0; i < k; i ++) {
            res[i] = priorityQueue.poll().getKey();
        }

        return res;
    }

}
